%%%%%%%%%%%%%%%%5
%\documentclass[12pt]{book}
%\usepackage{epsfig}
%\input tcilatex
%\begin{document}
%%%%%%%%%%%%

\section{Regulariza\c{c}\~{a}o}

\label{CAP-ILLPOSED-REG}

Um m\'{e}todo bastante utilizado na resolu\c{c}\~{a}o de problemas mal colocados
\'{e} chamado regulariza\c{c}\~{a}o, sendo inicialmente desenvolvido na d\'{e}cada
de 60, por Tikhonov \cite{TIKHONOV7701,TIKHONOV8701}. A id\'{e}ia b\'{a}sica
consiste em adicionar algum tipo de informa\c{c}\~{a}o \emph{a priori} ao
problema atrav\'{e}s de uma fun\c{c}\~{a}o n\~{a}o negativa, de forma a torn\'{a}-lo
bem condicionado e permitir, dessa forma, uma solu\c{c}\~{a}o \'{u}nica e
est\'{a}vel.

Utilizando-se ainda o problema descrito pela Equa\c{c}\~{a}o~\ref{EQAXY},
pode-se perceber que, como a aplica\c{c}\~{a}o de $\mathbf{K}$ no vetor 
$\mathbf{f}$ geralmente est\'{a} relacionada com alguma opera\c{c}\~{a}o de
alisamento, parte da informa\c{c}\~{a}o pode ser perdida
neste processo, dificultando a reconstru\c{c}\~{a}o da opera\c{c}\~{a}o inversa.
Da mesma forma, uma maneira de se tentar superar esta dificuldade \'{e}
agregar mais informa\c{c}\~{o}es ao processo de reconstru\c{c}\~{a}o, aumentando
assim a chance de reconstru\c{c}\~{a}o do vetor original \cite{GIROSSI9002}.

A solu\c{c}\~{a}o sugerida por Tikhonov \cite{TIKHONOV8701} est\'{a} representada na 
Equa\c{c}\~{a}o~\ref{EQTIKHO}, onde $\alpha $ \'{e} o chamado \emph{par\^{a}metro de regulariza\c{c}\~{a}o} 
e $L$ \'{e} algum tipo de operador linear, por exemplo 
$L\mathbf{f}=\mathbf{f}$, $\mathbf{f}^{^{\prime }}$ ou $\mathbf{f}^{^{\prime \prime }}$ ou
ainda $L\mathbf{f}=\mathbf{f}-\mathbf{\hat f}$, sendo $\mathbf{\hat f}$ a
representa\c{c}\~{a}o de alguma aproxima\c{c}\~{a}o conhecida de $\mathbf{f}$ \cite{RIELE8501}. 

O termo {\em regulariza\c{c}\~{a}o de ordem n} tamb\'{e}m \'{e} frequentemente encontrado, 
sendo que $n$ est\'{a} relacionado com o n\'{u}mero de derivadas realizadas
em $\mathbf{f}$, no segundo termo da Equa\c{c}\~{a}o~\ref{EQTIKHO}. O que se
espera \'{e} que, do conjunto de poss\'{\i}veis matrizes $\mathbf{f}$ tais que 
$\left\{ \mathbf{f}{:\left\| \mathbf{Kf}{-}\mathbf{g}\right\| \le \epsilon } \right\} $, 
uma seja escolhida de forma que a solu\c{c}\~{a}o apresente um
custo m\'{\i}nimo e que $\mathbf{f}$ convirga para a solu\c{c}\~{a}o de 
$\mathbf{Kf}=\mathbf{g}$ quando $\epsilon \to 0$ \cite{RIELE8501}.

%MathType!ZZhx47!ceaadaGcbiXGfnWdbaWcbiaHHbqeaOWabaaabiXGMbGawIIawMcacy
%ypduaaaeGedgKedAMag2IedEgacy5ycyjzamWdaaWcreGaikdaaOGa
%gUYafaaabiXGmjXGMbGawoMawsgad8aaaSqebiaIYaaaaaa!1143!
\begin{equation}
E_\alpha \left[ \mathbf{f}\right] =\left\| \mathbf{Kf}{-}\mathbf{g}\right\|
^2+\alpha \left\| {L}\mathbf{f}\right\| ^2  \label{EQTIKHO}
\end{equation}

\subsection{Fun\c{c}\~{a}o de Custo em Detalhes}

Inicialmente ser\'{a} apresentada uma an\'{a}lise mais gen\'{e}rica da fun\c{c}\~{a}o 
de custo, analisando a sua solu\c{c}\~{a}o atrav\'{e}s de pseudo-inversa e 
a utiliza\c{c}\~{a}o de t\'{e}cnicas como
regulariza\c{c}\~{a}o local e global. Depois, um exemplo bidimensional
mostrando a influ\^{e}ncia na procura do m\'{\i}nimo ser\'{a} apresentado,
permitindo uma visualiza\c{c}\~{a}o melhor de todo o processo. 
Uma dedu\c{c}\~{a}o similar pode ser encontrada no trabalho de Mark Orr \cite{MARKORR9601}.

\subsubsection{Caso Geral}

Considere a fun\c{c}\~{a}o de custo definida abaixo:

\begin{equation}
\begin{array}{cccc}
E\left[ \mathbf{f}\right] = & \underbrace{\frac 12\left\| \mathbf{Kf}-%
\mathbf{g}\right\| ^2} & + & \frac 12\underbrace{\mathbf{A}}\left\| 
\underbrace{\left( \mathbf{f}-\mathbf{\hat f}\right) }\right\| ^2 \\ 
& \left( 1\right)  &  & \left( 2\right) \;\;\;\left( 3\right) \;\;\;
\end{array}
\label{EQFUNENER1}
\end{equation}

Esta fun\c{c}\~{a}o de custo \'{e} ligeiramente diferente da apresentada na
Equa\c{c}\~{a}o~\ref{EQTIKHO}. Para tornar a an\'{a}lise mais curta optou-se por
um segundo termo onde exista alguma estimativa inicial de $\mathbf{f}$.
Uma solu\c{c}\~{a}o contendo
tamb\'{e}m derivadas primeira e segunda no termo de regulariza\c{c}\~{a}o 
pode ser encontrada no trabalho de
Riele \cite{RIELE8501}.

Os termos desta equa\c{c}\~{a}o est\~{a}o descritos a seguir.

\begin{enumerate}
\item
\textbf{Fun\c{c}\~{a}o custo original em sua forma matricial}. 
Neste caso, $\mathbf{K}$ \'{e} uma matriz $m\times n$, $\mathbf{f}$ e $\mathbf{g}$ s\~{a}o
vetores $n\times 1$.

\item
\textbf{Par\^{a}metros de regulariza\c{c}\~{a}o}. De forma mais
gen\'{e}rica, s\~{a}o escolhidos $n$ par\^{a}metros de regulariza\c{c}\~{a}o, todos
positivos. $\mathbf{A}$ \'{e} a matriz contendo todos estes par\^{a}metros,
sendo definida como:

\[
\mathbf{A}=\left[ 
\begin{array}{cccc}
\alpha _1 & 0 & \cdots  & 0 \\ 
0 & \alpha _2 & \cdots  & 0 \\ 
\vdots  & \vdots  & \ddots  & \vdots  \\ 
0 & 0 & \cdots  & \alpha _n
\end{array}
\right] 
\]

Este par\^{a}metro atua como um indicador de sufici\^{e}ncia. Valores pr\'{o}ximos
de zero indicam um conjunto de dados consistente para determinar $E\left[
f\right] $, sendo assim o problema irrestrito. Valores altos de $\alpha _i$
aumentam a necessidade de conhecimento {\em a priori}. Em geral n\~{a}o \'{e} muito
f\'{a}cil se estimar qual o valor ideal para o par\^{a}metro de regulariza\c{c}\~{a}o 
sendo que v\'{a}rias t\'{e}cnicas v\^{e}m sendo utilizadas com este
prop\'{o}sito, tais como Valida\c{c}\~{a}o Cruzada Generalizada 
(GCV - {\em ``Generalised Cross-Validation''}), {\em ``Leave-One-Out (LOO)''}  e crit\'{e}rio de informa\c{c}\~{a}o 
Bayesiana (ver  \cite{MARKORR9601} para mais detalhes sobre estas t\'{e}cnicas). 
A determina\c{c}\~{a}o do par\^{a}metro de
regulariza\c{c}\~{a}o pode ser encarada como um problema de otimiza\c{c}\~{a}o
n\~{a}o linear \cite{MARKORR9602}.

\item
\textbf{Fun\c{c}\~{a}o de regulariza\c{c}\~{a}o}. O vetor $\mathbf{\hat f}$
representa uma estimativa inicial para o problema. Em geral, o tipo de fun\c{c}\~{a}o 
de regulariza\c{c}\~{a}o utilizada ir\'{a} depender grandemente do
conhecimento que se tem do problema que est\'{a} se solucionando. 
Mais especificamente, para
a fun\c{c}\~{a}o de custo que vem sendo tratada, o que se nota \'{e} que a fun\c{c}\~{a}o 
de regulariza\c{c}\~{a}o permite uma estabilidade maior na solu\c{c}\~{a}o,
tornando a fun\c{c}\~{a}o de custo mais imune a ru\'{\i}dos e ao conjunto de
treinamento utilizado. Esta fun\c{c}\~{a}o ir\'{a} conduzir o problema para
solu\c{c}\~{o}es de norma m\'{\i}nima (nas vizinhan\c{c}as de $\mathbf{\hat f}$),
pois condena altos valores para $\mathbf{f}$. Isto se assemelha em muito
\`{a}s t\'{e}cnicas de \emph{pruning} \cite{RUSSEL9301} utilizada em redes
neurais, onde em geral os pesos sofrem algum tipo de penaliza\c{c}\~{a}o.
\end{enumerate}

O desenvolvimento da Equa\c{c}\~{a}o~\ref{EQFUNENER1} ser\'{a} feito em forma de somat\'{o}rio e,
por motivos de simplifica\c{c}\~{a}o, ser\'{a} usada, quando conveniente, a
rela\c{c}\~{a}o $\mathbf{\hat g}=\mathbf{Kf}$.  Assim, tem-se:

\begin{equation}
E\left[ \mathbf{f}\right] =\frac 12\sum\limits_i\left( \hat g_i-g_i\right)
^2+\frac 12\sum \alpha _i\left( f_i-\hat f_i\right) ^2
\end{equation}

Para se encontrar o valor m\'{\i}nimo, \'{e} necess\'{a}rio que se resolva um
sistema de $n$ equa\c{c}\~{o}es que ser\'{a} composto pelas derivadas em rela\c{c}\~{a}o 
as coordenadas do vetor $\mathbf{f}$, ou seja:

\[
\frac{\partial E}{\partial f_k}=0\;\;\;\;\;\;para\;k=1\ldots n
\]

Estas derivadas podem ser representada por:

\[
\frac{\partial E}{\partial f_k}=\sum\limits_i\left( \hat g_i-g_i\right)
K_{ik}+\alpha _kf_k-\alpha _k\hat f_k^{}=0
\]

\[
\sum\limits_iK_{ik}\hat g_i+\lambda _kf_k=\sum\limits_iK_{ik}g_i+\lambda
_k\hat f_k^{}
\]

N\~{a}o \'{e} dificil notar que este sistema pode ser escrito na forma
matricial como:

\[
\mathbf{K}^T\mathbf{\hat g}+\mathbf{Af}=\mathbf{K}^T\mathbf{g}+\mathbf{A\hat
f}
\]

\[
\mathbf{K}^T\mathbf{Kf}+\mathbf{Af}=\mathbf{K}^T\mathbf{g}+\mathbf{A\hat f}
\]

\[
\left( \mathbf{K}^T\mathbf{K}+\mathbf{A}\right) \mathbf{f}=\mathbf{K}^T%
\mathbf{g}+\mathbf{A\hat f}
\]

A solu\c{c}\~{a}o final se torna ent\~{a}o:

\begin{equation}
\mathbf{f}=\left( \mathbf{K}^T\mathbf{K}+\mathbf{A}\right) ^{-1}\mathbf{K}^T%
\mathbf{g}+\left( \mathbf{K}^T\mathbf{K}+\mathbf{A}\right) ^{-1}\mathbf{%
A\hat f}  \label{EQSOLUCAO}
\end{equation}

Esta equa\c{c}\~{a}o ser\'{a} a base para as pr\'{o}ximas an\'{a}lises.

\subsubsection{Pseudo Inversa}

Ao se fazer todos os par\^{a}metros de regulariza\c{c}\~{a}o iguais a zero, 
ou seja, $\mathbf{A}=\mathbf{0}$, obt\'{e}m-se a solu\c{c}\~{a}o 
por \textit{pseudo-inversa}, criada por Penrose 
\cite{PENROSE5501}, que \'{e} uma generaliza\c{c}\~{a}o da matriz inversa (ver 
Equa\c{c}\~{a}o \ref{EQSOLPINV}).
Matematicamente:

\begin{equation}
\mathbf{f=K}^{+}\mathbf{g}
\end{equation}

Onde $\mathbf{K}^{+}$ \'{e} o mesmo definido na Equa\c{c}\~{a}o \ref{EQSOLPINV}.

%\begin{equation}
%V=\left( A^TA\right) ^{-1}A^TB
%\end{equation}

Esta solu\c{c}\~{a}o ir\'{a} se comportar muito bem para problemas onde a matriz 
$\mathbf{K}$ possui rank completo. Nestes casos a pseudo-inversa existe e a
solu\c{c}\~{a}o do problema \'{e} \'{u}nica. Mas, \`{a} medida que a matriz 
$\mathbf{K}$ aumenta o seu condicionamento, a solu\c{c}\~{a}o \'{e} cada vez menos
est\'{a}vel, bem pouco imune a ru\'{\i}dos que possam aparecer. No caso
extremo, onde o rank de $\mathbf{K}$ n\~{a}o \'{e} mais completo, a
pseudo-inversa n\~{a}o existe mais e passa-se a ter infinitas solu\c{c}\~{o}es
para o problema. Devido a estas defici\^{e}ncias, este tipo de solu\c{c}\~{a}o
n\~{a}o ir\'{a} tratar com fidelidade um problema mal condicionado.

\subsubsection{Regulariza\c{c}\~{a}o Global}

Para a regulariza\c{c}\~{a}o global, teremos apenas um \'{u}nico par\^{a}metro de
regulariza\c{c}\~{a}o. Dessa forma, a matriz $\mathbf{A}$ pode ser substitu\'{\i}do por 
um escalar $\alpha $, resultando em:

\begin{equation}
\mathbf{f}=\left( \mathbf{K}^T\mathbf{K}+\alpha \mathbf{I}\right) ^{-1}%
\mathbf{K}^T\mathbf{g}+\alpha \left( \mathbf{K}^T\mathbf{K}+\alpha \mathbf{I}%
\right) ^{-1}\mathbf{\hat f}
\label{EQFUNENER3}
\end{equation}

\subsubsection{Regulariza\c{c}\~{a}o Local}

Finalmente, utilizando-se par\^{a}metros de regulariza\c{c}\~{a}o
diferenciados, passa-se a ter uma regulariza\c{c}\~{a}o local, que permite
tratar de maneira mais detalhada o problema. Em geral, n\~{a}o existe
nenhuma garantia de que a regulariza\c{c}\~{a}o local ir\'{a} se sair melhor
do que a global, estando isto novamente ligado ao problema que se est\'{a}
solucionando \cite{MARKORR9602}. A equa\c{c}\~{a}o \'{e} a inicialmente 
proposta:

\begin{equation}
\mathbf{f}=\left( \mathbf{K}^T\mathbf{K}+\mathbf{A}\right) ^{-1}\mathbf{K}^T%
\mathbf{g}+\left( \mathbf{K}^T\mathbf{K}+\mathbf{A}\right) ^{-1}\mathbf{%
A\hat f}
\end{equation}

\subsubsection{Polariza\c{c}\~{a}o e vari\^{a}ncia}

\label{CAP-ILLPOSED-REG-POLVAR}

Uma \'{u}ltima an\'{a}lise interessante que pode ser feita est\'{a} ligada com o
valor esperado para fun\c{c}\~{a}o de energia\footnote{As equa\c{c}\~{o}es sobre polariza\c{c}\~{a}o 
e vari\^{a}ncia apresentadas
nesta se\c{c}\~{a}o representam um detalhamento das encontradas
em \cite{MARKORR9601}, com modifica\c{c}\~{o}es introduzidas pelo autor.}, ou seja:

\begin{equation}
\bar E=\left\langle E\right\rangle =\frac 12\left\langle \left\| \mathbf{%
\hat g}-\mathbf{g}\right\| ^2\right\rangle   \label{EQESPERADA}
\end{equation}

Novamente, para simplifica\c{c}\~{a}o das express\~{o}es, ir\'{a} se usar 
$\mathbf{\hat g}$ e o seu valor m\'{e}dio, representado por $\mathbf{\bar g}=\left\langle 
\mathbf{\hat g}\right\rangle $. Desenvolvendo-se a Equa\c{c}\~{a}o \ref
{EQESPERADA}, tem-se:

\[
2\bar E=\left\langle \sum\limits_i\left( \hat g_i-g_i\right) ^2\right\rangle
=\left\langle \sum\limits_i\left( \hat g_i^2-2\hat g_i^{}g_i+g_i^2\right)
\right\rangle 
\]

\[
2\bar E=\sum\limits_ig_i^2-2\sum\limits_ig_i\left\langle \hat
g_i^{}\right\rangle +\sum\limits_i\left\langle \hat g_i^2\right\rangle
=\sum\limits_ig_i^2-2\sum\limits_ig_i\bar g_i+\sum\limits_i\left\langle \hat
g_i^2\right\rangle 
\]

Como a vari\^{a}ncia de $\hat g_i=\sum\limits_i{}_i\left\langle \hat
g_i^2\right\rangle -\sum\limits_i\bar g_i^2$, fica-se com:

\[
2\bar E=\sum\limits_iB_i^2-2\sum\limits_iB_i\bar
B_i+\sum\limits_i{}\left\langle \hat B_i^2\right\rangle -\sum\limits_i\bar
B_i^2+\sum\limits_i\bar B_i^2 
\]

Colocando-se os termos em uma ordem mais apropriada:

\[
2\bar E=\sum\limits_ig_i^2-2\sum\limits_ig_i\bar g_i+\sum\limits_i\bar
g_i^2+\sum\limits_i{}\left\langle \hat g_i^2\right\rangle -\sum\limits_i\bar
g_i^2
\]

\begin{equation}
\begin{array}{cccc}
\bar E= & \underbrace{\frac 12\sum\limits_i\left( g_i-\bar g_i\right) ^2} & +
& \underbrace{\frac 12\left\langle \sum\limits_i{}\left( \hat g_i-\bar
g_i\right) ^2\right\rangle } \\ 
& Polarizac\tilde ao &  & Vari\hat ancia
\end{array}
\label{EQPOLVAR}
\end{equation}

Dessa forma, o valor esperado para a fun\c{c}\~{a}o de custo \'{e} dado por um
termo de polariza\c{c}\~{a}o mais a vari\^{a}ncia. Em geral, espera-se que a
estimativa da energia seja n\~{a}o polarizada ou, em outras palavras, que 
$\mathbf{\bar g}=\mathbf{g}$. Mas, mesmo que isto possa acontecer, se a
vari\^{a}ncia \'{e} muito grande, o erro quadr\'{a}tico m\'{e}dio final ainda ser\'{a}
de valor elevado \cite{MARKORR9601}. Isto geralmente ir\'{a} ocorrer em problemas com
condicionamento alto, que se tornam sens\'{\i}veis ao ru\'{\i}do ou a escolha
dos dados.

A introdu\c{c}\~{a}o de um termo de penalidade (ou regulariza\c{c}\~{a}o) pode ser
ent\~{a}o encarada como uma tentativa de diminuir o erro quadr\'{a}tico m\'{e}dio
atrav\'{e}s da adi\c{c}\~{a}o de um termo de polariza\c{c}\~{a}o que ir\'{a} penalizar
valores altos de $\mathbf{f}$, direcionando a resposta para uma valor de
norma m\'{\i}nima \cite{MARKORR9601}. A quantidade de penalidade adicionada, como j\'{a}
anteriormente descrito, \'{e} controlada pelo par\^{a}metro de regulariza\c{c}\~{a}o $\alpha $.

%%%%%%%%%%%%%
%\bibliographystyle{plain}
%\bibliography{neural}
%\end{document}
%%%%%%%%%%%%%